Turnbull China Bikeride/Turnbull China Bikeride - Disc 2.iso/BARNET/COMPILER/SATHER/!Sather/Library/Graphs/sa/digraph

Text File | 1996-07-13 | 9KB | 263 lines

---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <[e-mail]>
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
-------------------------------------------------------------------
class DIGRAPH < $DIGRAPH{INT} is
   -- A default digraph implementation which uses integer nodes
   include DIGRAPH{INT};

   create: SAME is
      return create(#INT_STREAM(0));
   end;

end;
-------------------------------------------------------------------
class DIGRAPH{NTP}  < $DIGRAPH{NTP} is
   -- This is a directed graph which permits arbitrary nodes of type
   -- NTP.  This is the default graph implementation. NTP is the node
   -- type i.e the unique node index The actual nodes of the graph may
   -- be supplied by the user of this class, during the add_node.  The
   -- digraph is implemented by two hash mappings from nodes to
   -- parents and nodes to outgoing. There is also a separate list of
   -- nodes.

   private include COMPARE{NTP} elt_eq->node_equal;
   include DIGRAPH_INCL{NTP};

   private attr node_generator: $SUCC_STREAM{NTP}; -- Generator of nodes
   -- which is used by add_node. If a node generator is not provided
   -- at creation time, then add_node cannot be used, since the graph
   -- does not know how to create new unique nodes.

   private attr node_list: FLIST{NTP}; -- List of nodes in the graph
   private attr incoming_map: FMULTIMAP{NTP,NTP};
   private attr outgoing_map: FMULTIMAP{NTP,NTP};
   -- Keep both around since it is quite expensive to derive one
   -- from the other.

   create: SAME is
      -- Create a new digraph and return it. Since a node
      -- generator is not specified, it will not be possible
      -- to call the "add_node:NTP" function, since the graph
      -- will not know how to create new unique nodes.
      -- All the data structures can be initialized with void
      res ::= new;
      res.incoming_map := #FMULTIMAP{NTP,NTP};
      res.outgoing_map := #FMULTIMAP{NTP,NTP};
      res.node_list := #;
      return(res)
   end;

   create(node_gen: $SUCC_STREAM{NTP}): SAME pre ~void(node_gen) is
      -- Create a new digraph. Store "node_gen" as a generator
      -- of nodes, so that when "add_node: NTP" is called it
      -- can generate unique new nodes.
      res: SAME := create;
      res.node_generator := node_gen;
      return res;
   end;

   -- ------------------- Initialization ------------------
   add_node: NTP is
      -- Add a new node and return the index
      if void(node_generator) then
     raise #GRAPH_EXC(self,"add_node",self,
              "Cannot call add_node: NTP on this graph."
              " No node generator was provided");
      else
     -- Get the next unique node
     n: NTP := node_generator.next;
     -- If it is really unique, add it to the list
     assert ~has_node(n);
     node_list := node_list.push(n);
     return n;
      end;
   end;

   add_node(n: NTP): NTP is
      -- Add the node "n". In this kind of hash digraph, the node
      -- index returned is guaranteed to be the same as the node
      -- "n". Note that this is not generally true for graphs
      if ~has_node(n) then node_list := node_list.push(n); end;
      return n;
   end;


   add_node(n: NTP) is
      -- Short hand for "add_node(n:NTP): NTP" that is only valid
      -- for this sort of graph, where the user specifies the node
      -- type.
      if ~has_node(n) then node_list := node_list.push(n); end;
   end;

   connect(e: DIEDGE{NTP}) is
      -- Connect source to target. No change if the edge already exists
      -- Add the nodes if they do not exist
      s ::= e.first; t ::= e.second;
      if has_edge(#DIEDGE{NTP}(s,t)) then return; end;
      if ~has_node(s) then add_node(s) end;
      if ~has_node(t) then add_node(t) end;
      outgoing_map := outgoing_map.insert(s,t);
      incoming_map := incoming_map.insert(t,s);
   end;

   -- ------------------- Removal -------------------------
   delete_node(n: NTP) is
      -- Delete a node from the graph, and all its accompanying edges
      node_list := node_list.delete_elt(n);
      incoming_map := incoming_map.delete_all(n);
      outgoing_map := outgoing_map.delete_all(n);
   end;

   disconnect(e: DIEDGE{NTP}) is
      -- Deletes the edge "e".
      dest ::= e.second; src ::= e.first;
      incoming_map := incoming_map.delete(dest,src);
      outgoing_map := outgoing_map.delete(src,dest);
   end;

   -- ------------------- Query --------------------------
   has_node(n: NTP): BOOL is return node_list.has(n) end;

   has_edge(e: DIEDGE{NTP}): BOOL is
      s ::= e.first; t ::= e.second;
      if ~has_node(s) or ~has_node(t) then return false
      else return incoming_map.has_pair(t,s);   end;
   end;

   -- ------------------- Measurement ---------------------
   n_nodes: INT is return node_list.size end;

   n_neighbors(n: NTP): INT pre has_node(n) is
      -- Returns the number of neighbors of "n"
      -- (nodes are only counted once)
      i: FLIST{NTP} := incoming_map.danger_multi_get(n);
      o: FLIST{NTP} := incoming_map.danger_multi_get(n);
      if i.size = 0 then return o.size
      elsif o.size = 0 then return i.size
      else return i.union(o).size end;
   end;

   n_incoming(n: NTP): INT pre has_node(n) is
      -- Number of incoming edges from node "n"
      return(incoming_map.n_targets(n));
   end;

   n_outgoing(n: NTP): INT pre has_node(n) is
      -- Number of outgoing edges from node "n"
      return(outgoing_map.n_targets(n));
   end;

   n_edges: INT is
      -- Returns the number of edges in the graph, making sure
      -- each edge is only counted once
      res ::= 0;
      loop n ::= node!; res := res+n_incoming(n); end;
      return res;
   end;

   -- ------------------- Cursor --------------------------
   node!: NTP is loop yield node_list.elt! end; end;

   incoming!(once n: NTP): NTP pre has_node(n) is
      loop yield incoming_map.target!(n) end;
   end;

   outgoing!(once n: NTP): NTP pre has_node(n) is
      loop yield outgoing_map.target!(n) end;
   end;

   edge!: DIEDGE{NTP} is
      -- Return all edges in the graph
      loop n ::= node!;
     loop inc ::= incoming!(n); yield #DIEDGE{NTP}(inc,n); end;
     -- loop outg ::= outgoing!(n); yield #DIEDGE{NTP}(n,outg); end;
      end;
   end;

   -- ------------------  COMPARING ---------------------------------
   is_identical(g: SAME): BOOL is
      -- Check whether the two graphs have the same nodes, edges in
      -- the same order
      if g.n_nodes /= n_nodes then return false end;
      loop  if ~node_equal(node!,g.node!) then return false end end;
      loop n::= node!;
     if ~incoming_map.get_all(n).equals(g.incoming_map.get_all(n)) then
        return false
     elsif ~outgoing_map.get_all(n).equals(g.outgoing_map.get_all(n)) then
        return false
     end;
      end;
      return true
   end;

   -- Some convenient calls into algorithm classes that are not required
   -- by the abstraction
   source!: NTP is
      -- Yield all the source nodes with n_incoming = 0 in self
      loop yield DIGRAPH_ALG{NTP,SAME}::source!(self) end;
   end;

   sink!: NTP is
      -- Yield all the sink nodes (with n_outgoing = 0) in self
      loop yield DIGRAPH_ALG{NTP,SAME}::sink!(self) end;
   end;

   bf!(once n: NTP): NTP is
      -- Yield all nodes in breadth first order
      loop yield DIGRAPH_ALG{NTP,SAME}::bf!(self,n) end;
   end;

   df!(once n: NTP): NTP is
      -- Yield all nodes in depth first order
      loop yield DIGRAPH_ALG{NTP,SAME}::df!(self,n) end;
   end;

   topo_order!: NTP is
      -- Yield the nodes of self in some topologically sorted orer
      loop yield DIGRAPH_ALG{NTP,SAME}::topo_order!(self) end;
   end;

   layer!: SET{NTP} is
      -- Peel off successive layers from the graph, starting with the
      -- root set. Stop when no more roots (nodes with no incoming edges)
      -- can be found.
      loop yield DIGRAPH_ALG{NTP,SAME}::layer!(self) end;
   end;

   is_topo_order(n: $ARR{NTP}):BOOL is
      -- Return true if the nodes in "n" do not violate the precedence
      -- relations expressed by the graph "self"
      return DIGRAPH_ALG{NTP,SAME}::is_topo_order(self,n)
   end;


   private check_node(n: NTP,routine_name: STR): BOOL is
      if has_node(n) then return true
      else
     #ERR+routine_name+" received a node not in the graph\n";
     return false;
      end;
   end;


-- Adaptors
--   reverse_graph: DIGRAPH_REVERSE_VIEW{NTP} is
--      return(#DIGRAPH_REVERSE_VIEW{NTP}(self));
--   end;

--   subgraph: DIGRAPH_SUBGRAPH_VIEW{NTP} is
--      return(#DIGRAPH_SUBGRAPH_VIEW{NTP}(self));
--   end;

--   undirected: DIGRAPH_UNDIRECTED_VIEW{NTP} is
--      return(#DIGRAPH_UNDIRECTED_VIEW{NTP}(self));
--   end;

end; -- class DIGRAPH{NTP}
-------------------------------------------------------------------